\section{代换法}

\section{递归树方法}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item
  \item
  \item \textbf{画出$T(n) = 4T(\lfloor n/2 \rfloor) + cn$的递归树，并给出其解的渐近确界，其中$c$是一个常数。然后，用代换法证明你给出的界。}

        第$i$层结点的值为$c(\lfloor n/2^i \rfloor)$，$i \geqslant 0$，最后一层为$T(1)$，即$\lfloor n/2^i \rfloor = 1$，因此递归树一共有$i = \text{lg}n$层。

        每一层的结点个数为$4^i$，因此每一层的总代价为$4^i \cdot c(\lfloor n/2^i \rfloor)$，其中最后一层的总代价为$4^{\text{lg}n} \cdot T(1) = \Theta(4^{\text{lg}n}) = \Theta(n^{\text{lg}4}) = \Theta(n^2)$。于是可以得到整棵递归树的代价：
\begin{align}
  T(n) &= \sum_{i=0}^{\text{lg}n-1} 4^i \cdot c(\lfloor n/2^i \rfloor) + \Theta(n^2) \nonumber \\
       &\leqslant \sum_{i=0}^{\text{lg}n-1} 4^i \cdot \frac{cn}{2^i} + \Theta(n^2) \nonumber \\
       &= cn \sum_{i=0}^{\text{lg}n-1} 2^i + \Theta(n^2) \nonumber \\
       &= cn \cdot \frac{2^{\text{lg}n} - 1}{2 - 1} + \Theta(n^2) \nonumber \\
       &= cn(n - 1) + \Theta(n^2) \nonumber \\
       &= cn^2 - cn + \Theta(n^2) = \Theta(n^2)
\end{align}
        因此这棵递归树的渐近确界为$\Theta(n^2)$。现在用代换法进行证明，假设$T(\lfloor n/2 \rfloor) \leqslant c(\lfloor n/2 \rfloor)^2$，则：
\begin{align}
  T(n) &= 4T(\lfloor n/2 \rfloor) + cn \nonumber \\
       &\leqslant 4c(\lfloor n/2 \rfloor)^2 + cn \nonumber \\
       &\leqslant 4c\left(\frac{n}{2}\right)^2 + cn = cn^2 + cn \leqslant cn^2
\end{align}
\end{enumerate}

\section{主方法}

\begin{enumerate}[label=\textbf{\thesection{}-\arabic*}]
  \item \textbf{用主方法来给出下列递归式紧确的渐近界:}
        \begin{enumerate}[label=\textbf{\alph*)}]
          \item $T(n) = 4T(n/2) + n$

                在这个递归式中，$a = 4$，$b = 2$，$f(n) = n$，则$n^{\text{log}_{b}a} = n^{\text{log}_{2}4} = n^2$。因为$f(n) < n^{\text{log}_{b}a}$，尝试主定理的第一种情况是否成立。由于$f(n) = O(n^{\text{log}_{b}a-\varepsilon}) = O(n^{\text{log}_{2}4-1})$，其中$\varepsilon = 1$，因此满足第一种情况，则$T(n) = \Theta(n^{\text{log}_{b}a}) = \Theta(n^2)$。

          \item $T(n) = 4T(n/2) + n^2$

                在这个递归式中，$a = 4$，$b = 2$，$f(n) = n^2$，则$n^{\text{log}_{b}a} = n^{\text{log}_{2}4} = n^2$。因为$f(n) = \Theta(n^{\text{log}_{b}a}) = \Theta(n^2)$，所以满足主定理的第二种情况，因此$T(n) = \Theta(n^{\text{log}_{b}a}\text{lg}n) = \Theta(n^2\text{lg}n)$。

          \item $T(n) = 4T(n/2) + n^3$

                在这个递归式中，$a = 4$，$b = 2$，$f(n) = n^3$，则$n^{\text{log}_{b}a} = n^{\text{log}_{2}4} = n^2$。因为$f(n) > n^{\text{log}_{b}a}$，尝试主定理的第三种情况是否成立。首先$f(n) = \Omega(n^{\text{log}_{b}a+\varepsilon}) = \Omega(n^{\text{log}_{2}4+1})$，其中$\varepsilon = 1$。其次对足够大的$n$，要使$af(n/b) \leqslant cf(n)$成立，则：
\begin{align}
  4f\left(\frac{n}{2}\right) &\leqslant cf(n) \nonumber \\
  4\left(\frac{n}{2}\right)^3 &\leqslant cn^3 \nonumber \\
  c &\geqslant \frac{1}{2}
\end{align}
                存在常数$\frac{1}{2} \leqslant c < 1$，因此满足第三种情况，则$T(n) = \Theta(f(n)) = \Theta(n^3)$。
        \end{enumerate}

  \item \textbf{某个算法$A$的运行时间由递归式$T(n) = 7T(n/2) + n^2$表示; 另一个算法$A'$的运行时间为$T'(n) = aT'(n/4) + n^2$。若要$A'$比$A$更快，那么$a$的最大整数值是多少？}

        对于递归式$T(n)$，$f(n) = n^2$，$n^{\text{log}_{b}a} = n^{\text{log}_{2}7}$，且存在常数$\varepsilon$使得$f(n) = O(n^{\text{log}_{b}a-\varepsilon})$，满足主定理的第一种情况，因此$T(n) = \Theta(n^{\text{log}_{2}7})$。

        对于递归式$T'(n)$，$f(n) = n^2$，$n^{\text{log}_{b}a} = n^{\text{log}_{4}a}$。若要求出使算法$A'$比$A$快的最大整数$a$，必定得使递归式$T'(n)$满足主定理的第一种情况，因为只有第一种情况下$a$的值才是最大的。因此$T'(n) = \Theta(n^{\text{log}_{4}a})$。

        因为$A'$比$A$快，所以：
\begin{align}
  \Theta(n^{\text{log}_{4}a}) &< \Theta(n^{\text{log}_{2}7}) \nonumber \\
  n^{\text{log}_{4}a} &< n^{\text{log}_{2}7} \nonumber \\
  \text{log}_{4}a &< \text{log}_{2}7 \nonumber \\
  \frac{\text{log}_{2}a}{\text{log}_{2}4} &< \text{log}_{2}7 \nonumber \\
  \text{log}_{2}a &< \text{log}_{2}49 \nonumber \\
  a &< 49
\end{align}
        因此若要$A'$比$A$更快，那么$a$的最大整数值是48。

  \item \label{sec:4.3-3}\textbf{用主方法证明二分查找递归$T(n) = T(n/2) + \Theta(1)$的解是$T(n) = \Theta(\text{lg}n)$。（二分查找的描述见练习2.3-5）}

        $f(n) = \Theta(1)$，$n^{\text{log}_{b}a} = 1$，所以$f(n) = \Theta(n^{\text{log}_{b}a})$，满足主定理的第二种情况，因此$T(n) = \Theta(n^{\text{log}_{b}a}\text{lg}n) = \Theta(\text{lg}n)$。

  \item \textbf{主方法能否应用于递归式$T(n) = 4T(n/2) + n^2\text{lg}n$？为什么？给出此递归式的渐近上界。}

        $f(n) = n^2\text{lg}n$，$n^{\text{log}_{b}a} = n^2$，尝试是否满足主定理的第三种情况。对任意正常数$\varepsilon$，比值$f(n)/n^{\text{log}_{b}a} = \text{lg}n$渐近小于$n^\varepsilon$，因此不满足第三种情况，不能用主方法求解递归式。

        现在用递归树方法求解此递归式的渐近上界。第$i$层结点的值为$(n/2^i)^2\text{lg}(n/2^i)$，$i \geqslant 0$，最后一层为$T(1)$，即$n/2^i = 1$，因此递归树一共有$i = \text{lg}n$层。

        每一层的结点个数为$4^i$，因此每一层的总代价为$4^i \cdot (n/2^i)^2\text{lg}(n/2^i) = n^2\text{lg}(n/2^i)$，其中最后一层的总代价为$4^{\text{lg}n} \cdot T(1) = n^2T(1) = \Theta(n^2)$。于是可以得到整棵递归树的代价：
\begin{align}
  T(n) &= \sum_{i=0}^{\text{lg}n-1} n^2\text{lg}\frac{n}{2^i} + \Theta(n^2) \nonumber \\
       &= \sum_{i=0}^{\text{lg}n-1} n^2(\text{lg}n - i) + \Theta(n^2) \nonumber \\
       &= \sum_{i=0}^{\text{lg}n-1} n^2\text{lg}n - n^2\sum_{i=0}^{\text{lg}n-1} i + \Theta(n^2) \nonumber \\
       &= n^2(\text{lg}n)^2 - n^2 \cdot \frac{(\text{lg}n - 1)\text{lg}n}{2} + \Theta(n^2) \nonumber \\
       &= \frac{n^2\text{lg}n(\text{lg}n - 1)}{2} + \Theta(n^2) \nonumber \\
       &= O(n^2\text{lg}n)
\end{align}

  \item \textbf{考虑在某个常数$c < 1$时的规则性条件$af(n/b) \leqslant cf(n)$，此条件是主定理第三种情况的一部分。举一个常数$a \geqslant 1$，$b > 1$以及一个函数$f(n)$，满足主定理第三种情况中的除了规则性条件之外的所有条件的例子。}
\end{enumerate}

\section*{思考题}
\addcontentsline{toc}{section}{思考题}

\begin{enumerate}[label=\textbf{\thechapter{}-\arabic*}]
  \item \textbf{递归式的例子}

        {\kaishu 给出下列递归式的渐近上下界。假设$T(n)$是个常数，$n \leqslant 2$。使所给出的界尽量紧确。并给出证明。}

        \begin{enumerate}[label=\alph*)]
          \item $T(n) = 2T(n/2) + n^3$

                $f(n) = n^3$，$n^{\text{log}_{b}a} = n$，有$f(n) = \Omega(n^{\text{log}_{b}a+2})$，且对足够大的$n$，存在常数$c < 1$满足$af(n/b) \leqslant cf(n)$，其中$1/4 \leqslant c < 1$，递归式符合主定理的第三种情况，因此$T(n) = \Theta(f(n)) = \Theta(n^3)$。

          \item $T(n) = T(9n/10) + n$

                $f(n) = n$，$n^{\text{log}_{b}a} = 1$，有$f(n) = \Omega(n^{\text{log}_{b}a+1})$，且对足够大的$n$，存在常数$c < 1$满足$af(n/b) \leqslant cf(n)$，其中$9/10 \leqslant c < 1$，递归式符合主定理的第三种情况，因此$T(n) = \Theta(f(n)) = \Theta(n)$。

          \item $T(n) = 16T(n/4) + n^2$

                $f(n) = n^2$，$n^{\text{log}_{b}a} = n^2$，有$f(n) = n^{\text{log}_{b}a}$，递归式符合主定理的第二种情况，因此$T(n) = \Theta(n^{\text{log}_{b}a}\text{lg}n) = \Theta(n^2\text{lg}n)$。

          \item $T(n) = 7T(n/3) + n^2$

                $f(n) = n^2$，$n^{\text{log}_{b}a} = n^{\text{log}_{3}7}$，因为$\text{log}_{3}7 < 2$，所以存在常数$\varepsilon > 0$满足$f(n) = \Omega(n^{\text{log}_{b}a+\varepsilon})$。且对足够大的$n$，存在常数$c < 1$满足$af(n/b) \leqslant cf(n)$，其中$7/9 \leqslant c < 1$，递归式符合主定理的第三种情况，因此$T(n) = \Theta(f(n)) = \Theta(n^2)$。

          \item $T(n) = 7T(n/2) + n^2$

                $f(n) = n^2$，$n^{\text{log}_{b}a} = n^{\text{lg}7}$，因为$\text{lg}7 > 2$，所以存在常数$\varepsilon > 0$满足$f(n) = O(n^{\text{log}_{b}a-\varepsilon})$。递归式符合主定理的第一种情况，因此$T(n) = \Theta(n^{\text{log}_{b}a}) = \Theta(n^{\text{lg}7})$。

          \item $T(n) = 2T(n/4) + \sqrt{n}$

                $f(n) = \sqrt{n}$，$n^{\text{log}_{b}a} = \sqrt{n}$，有$f(n) = n^{\text{log}_{b}a}$，递归式符合主定理的第二种情况，因此$T(n) = \Theta(n^{\text{log}_{b}a}\text{lg}n) = \Theta(\sqrt{n}\text{lg}n)$。

          \item $T(n) = T(n - 1) + n$

                使用递归树方法进行求解，$T(n) = \sum_{i=1}^n i = \Theta(n^2)$。

                再使用代换法进行证明，首先证明$T(n) = O(n^2)$。假设$T(n - 1) \leqslant c(n - 1)^2$，$c > 0$，则：
\begin{align}
  T(n) &= T(n - 1) + n \nonumber \\
       &\leqslant c(n - 1)^2 + n \nonumber \\
       &= cn^2 - 2cn + c + n \nonumber \\
       &\leqslant cn^2
\end{align}
                当且仅当$-2cn + c + n \leqslant 0$时成立，即$n(1 - 2c) + c \leqslant 0$。此条件在$c = 1$及$n \geqslant 1$时满足。

                再证明$T(n) = \Omega(n^2)$。同理可得$T(n) \geqslant cn^2$，当且仅当$-2cn + c + n \geqslant 0$时成立，此条件在$0< c \leqslant 1/2$及$n \geqslant 0$时满足。

                综上，$T(n) = \Theta(n^2)$。

          \item \label{sec:4-1-h}$T(n) = T(\sqrt{n}) + 1$

                设$n = 2^m$，则$T(2^m) = T(2^{m/2}) + 1$，再设$T(2^m) = S(m)$，则$S(m) = S(m/2) + 1$。

                运用主定理求解递归式$S(m)$。$f(m) = 1$，$m^{\text{log}_{b}a} = 1$，满足主定理的第二种情况，则$S(m) = \Theta(m^{\text{log}_{b}a}\text{lg}m) = \Theta(\text{lg}m)$。因此$T(n) = T(2^m) = S(m) = \Theta(\text{lg}m) = \Theta(\text{lg}\text{lg}n)$。
        \end{enumerate}

  \item \textbf{找出所缺的整数}

        {\kaishu 某数组$A[1\texttt{..}n]$含有所有从0到$n$的整数，但其中有一个整数不在数组中。通过利用一个辅助数组$B[0\texttt{..}n]$来记录$A$中出现的整数，很容易在$O(n)$时间内找出所缺的整数。但在这个问题中，我们却不能由一个单一操作来访问$A$中的一个完整整数，因为$A$中的元素是以二进制表示的。我们所能用的唯一操作就是“取$A[i]$的第$j$位”，这个操作所花时间为常数。}

        {\kaishu 证明: 如果访问数组$A$中信息的唯一方式是这种单一位操作，仍能在$O(n)$时间内找出所缺的整数。$A$之外的任一完整整数仍可以由一个单一操作来访问。}

        先来看一个例子，假设这是一个0$\sim$5的序列，每一个数的二进制表示如下：
\begin{table}[H]
  \caption{0$\sim$5的二进制表示}
  \centering
  \begin{tabular}{cc|cc}
    \hline
    数字（十进制） & 对应的二进制 & 数字（十进制） & 对应的二进制 \\
    \hline
    0 & 000 & 3 & 011 \\
    \hline
    1 & 001 & 4 & 100 \\
    \hline
    2 & 010 & 5 & 101 \\
    \hline
  \end{tabular}
\end{table}
        为了更好地展现其中的规律，所有数的二进制表示都加上了前导0，使得它们二进制表示的位数相同。这里规定二进制数左边第一位为“最高位”，右边第一位为“最低位”。可以得出，{\kaishu 对于整数$n$，它的二进制表示的位数最小为$\lceil \text{lg}(n + 1) \rceil$。}

        先来观察所有数的最高位，最高位为“0”的数有4个，最高位为“1”的数有2个。其中最高位为“0”的数的个数恰好等于$2^{(\lceil \text{lg}(n + 1) \rceil - 1)}$，$n$代表序列的最大数，这里即是5。

        我们把最高位为“1”的两个数去掉，即4和5，再来观察剩余数字的二进制表示：
\begin{table}[H]
  \caption{0$\sim$3的二进制表示}
  \centering
  \begin{tabular}{cc|cc}
    \hline
    数字（十进制） & 对应的二进制 & 数字（十进制） & 对应的二进制 \\
    \hline
    0 & 00 & 2 & 10 \\
    \hline
    1 & 01 & 3 & 11 \\
    \hline
  \end{tabular}
\end{table}
        这次最高位为“0”的个数为2，最高位为“1”的个数也为2。而最高位为“0”的数的个数依旧等于$2^{(\lceil \text{lg}(n + 1) \rceil - 1)}$，这里$n = 3$。

        现在回到最开始，仍然是一个0$\sim$5的序列，不过这次少了一个数：
\begin{table}[H]
  \caption{0$\sim$5的二进制表示}
  \centering
  \begin{tabular}{cc|cc}
    \hline
    数字（十进制） & 对应的二进制 & 数字（十进制） & 对应的二进制 \\
    \hline
    0 & 000 & 3 & 011 \\
    \hline
    ? & ??? & 4 & 100 \\
    \hline
    2 & 010 & 5 & 101 \\
    \hline
  \end{tabular}
\end{table}
        当然，我们都知道这个数是“1”，不过假设你是不知道的。用前面的方法再观察一次，这次最高位为“0”的数有3个，最高位为“1”的数有2个，你能猜出缺少的那个数的最高位是“0”还是“1”吗？肯定是“0”。刚才的几个例子已经能够得出{\kaishu 对于一个0$\sim$$n$的序列，必定包含$2^{(\lceil \text{lg}(n + 1) \rceil - 1)}$个最高位为“0”的数。}

        在确定了这个缺少的数的最高位为“0”之后，继续在其它所有最高位为“0”的数中观察：
\begin{table}[H]
  \caption{0$\sim$3的二进制表示}
  \centering
  \begin{tabular}{cc|cc}
    \hline
    数字（十进制） & 对应的二进制 & 数字（十进制） & 对应的二进制 \\
    \hline
    0 & 00 & 2 & 10 \\
    \hline
    ? & ?? & 3 & 11 \\
    \hline
  \end{tabular}
\end{table}
        你恐怕已经知道这次该怎么做了，我们需要再次确定这个缺少的数的最高位。通过比较当前最高位为“0”的数的个数与$2^{(\lceil \text{lg}(n + 1) \rceil - 1)}$的大小，便可以很方便地确定缺少数的最高位是“0”还是“1”。很顺利得，我们知道了这个缺少的数的最高位为“0”。以此类推，最终确定我们想要找的数就是“1”。

        从上面的实例可以看出，通过不断地对序列所有数的最高位进行观察，便可以找到那个所缺的数字。这个过程用伪代码表示如下，{\kaishu 注意这里对于数组下标的定义遵照CLRS书中的约定，即$A[i]$代表数组$A$中的第$i$个元素，而实际编程中一般表示第$i - 1$个元素。}
\begin{alltt}
FIND-MISSING-INTEGER(\(A\), \(n\), \(M\), \(i\))
    \(\triangleright\) \(A\)代表缺少一个数的序列，\(n\)代表序列 \(A\)中的最大数（同时也是序列 \(A\)的元素个数），\(M\)代表存放所缺数各个二进制位的数组，\(i\)代表上一次在 \(M\)中存放的元素下标（初始为\(1\)）

    \(\triangleright\) 递归式的结束条件，即序列 \(A\)中只有一个数时，这时需要得到所缺数的最低位
    if \(n=1\)
        then if \(i\ne2\)
                 \(\triangleright\) 上一次在 \(M\)中存放的二进制位并不是倒数第二位（如果把最低位看作倒数第一位），需要在存入最低位之前先把上一次存放的至倒数第二位之间的二进制位存入 \(M\)
                 then for \(j\gets2\) to \(i-1\)
                          \(\triangleright\) \(A[1]\sb{j}\)表示序列 \(A\)中第 \(1\)个元素的二进制表示的第 \(j\)位，下同
                          do \(M[j]\gets{}A[1]\sb{j}\)
             \(M[1]\gets1-A[1]\sb{1}\)
             return

    \(\triangleright\) 初始化两个分别用来存放最高位为“\(0\)”和“\(1\)”的数的数组
    create arrays \(L[1\text{..}n]\) and \(R[1\text{..}n]\)

    \(\triangleright\) 得到当前序列最大数的二进制表示的位数
    \(bits_num\gets\lceil\text{lg}(n+1)\rceil\)

    \(\triangleright\) 将最高位为“\(0\)”的数存放到数组 \(L\)中，最高位为“\(1\)”的数存放到数组 \(R\)中
    \(a\gets1\)
    \(b\gets1\)
    for \(j\gets1\) to \(n\)
        do if \(A[j]\sb{bits_num}=0\)
               then \(L[a]\gets{}A[j]\)
                    \(a\gets{}a+1\)
               else \(R[b]\gets{}A[j]\)
                    \(b\gets{}b+1\)

    \(\triangleright\) 通过比较数组 \(L\)的长度来确定所缺数的最高位是“\(0\)”还是“\(1\)”
    if \(length[L]<2\sp{bits_num-1}\)
        then \(M[bits_num]\gets0\)
             \(i\gets{}bits_num\)
             FIND-MISSING-INTEGER(\(L\), \(2\sp{bits_num-1}-1\), \(M\), \(i\))
        else if \(i=1\)
                 \(\triangleright\) \(i=1\)即代表这是第一次执行
                 then \(M[bits_num]\gets1\)
                      \(i\gets{}bits_num\)
                      FIND-MISSING-INTEGER(\(R\), \(n-2\sp{bits_num-1}\), \(M\), \(i\))
                 else \(\triangleright\) \(last_bit\)代表理论上上一次在 \(M\)中存放的元素下标
                      \(last_bit\gets\lceil\text{lg}(n-2\sp{bits_num-1}+1)\rceil+1\)
                      \(\triangleright\) 但有时还是会出现理论值（\(last_bit\)）与实际值（\(i\)）不相等的情况\footnote{\textrm{比如\(A[1\texttt{..}10]\)，所缺数为9，在第二次递归时就会发生这种情况。}}，这时就需要把中间跳过的二进制位都补上
                      if \(i\ne{}last_bit\)
                          then for \(j\gets{}last_bit\) to \(i-1\)
                                   do \(M[j]\gets{}A[n]\sb{j}\)
                      \(M[bits_num]\gets1\)
                      \(i\gets{}bits_num\)
                      FIND-MISSING-INTEGER(\(R\), \(n-2\sp{bits_num-1}\), \(M\), \(i\))
\end{alltt}
        通过上面的伪代码得出该算法的递归式为：
\begin{equation}
  T(n) = T(2^{\lceil\text{lg}(n + 1)\rceil - 1} - 1) + cn
\end{equation}
        现在用代换法求解递归式，假设$T(n) = O(n)$，当$n = 2^{\lceil\text{lg}(n + 1)\rceil - 1} - 1$时成立，则：
\begin{align}
  T(n) &= T(2^{\lceil\text{lg}(n + 1)\rceil - 1} - 1) + cn \nonumber \\
       &\leqslant c(2^{\lceil\text{lg}(n + 1)\rceil - 1} - 1) + cn \nonumber \\
       &\leqslant c(2^{\text{lg}(n + 1)} - 1) + cn \nonumber \\
       &= c(n + 1 - 1) + cn \nonumber \\
       &= 2cn
\end{align}
        证得$T(n) = O(n)$，Q.E.D.

        {\kaishu 算法参考资料: }\url{http://cs.nyu.edu/courses/summer08/G22.1170-001/hw02-soln.pdf}

  \item \textbf{参数传递的代价}

        {\kaishu 整个这本书中，我们都假定过程调用中的参数传递所花时间为常数，即使所传递的是个$N$个元素的数组也是一样。这个假设对大多数系统都是有效的，因为当参数为数组时，所传递的只是指向该数组的指针，而不是该数组本身。本题讨论三种参数传递策略:}

        \begin{enumerate}[label=\arabic*)]
          \item {\kaishu 数组由一个指针来传递。时间$ = \Theta(1)$。}
          \item {\kaishu 参数数组通过复制而传递。时间$ = \Theta(N)$，$N$是该数组的大小。}
          \item {\kaishu 一个数组在被传递时，仅拷贝被调用过程可能引用的数组的子域。若传递的是子树组$A[p\texttt{..}q]$。时间$ = \Theta(p - q + 1)$。}
        \end{enumerate}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 考虑在一个已排序的数组中找一个数的递归二叉查找算法（见练习2.3-5）。针对上面的三种参数传递策略，给出最坏情况运行时间的递归式，并给出其解的上界。可以设$N$为原问题的规模，$n$为子问题的规模。}
          \item {\kaishu 重做2.3.1节中MERGE-SORT的a)部分。}
        \end{enumerate}

        \begin{enumerate}[label=\alph*)]
          \item 二分查找用伪代码表示如下：
\begin{alltt}
BINARY-SEARCH(\(A\), \(n\), \(p\), \(q\))
    \(\triangleright\) \(A\)为已排序数组，\(n\)为想要查找的数字，\(p\)为数组的下界，\(q\)为数组的上界

    \(a\gets\lfloor(p+q) / 2\rfloor\)

    if \(n=A[a]\)
        then return \(a\)
        else if \(p=q\)
                 then return NIL

    if \(n<A[a]\)
        then return BINARY-SEARCH(\(A\), \(n\), \(p\), \(a\))
        else return BINARY-SEARCH(\(A\), \(n\), \(a+1\), \(q\))
\end{alltt}
                下面分别就上面三种参数传递策略进行讨论。
                \begin{enumerate}[label=\arabic*)]
                  \item 这种策略就是通常考虑的情况，因此和\hyperref[sec:4.3-3]{4.3-3}所说的一样，递归式为$T(n) = T(n/2) + \Theta(1)$，递归式的解为$T(n) = \Theta(\text{lg}n)$。
                  \item 这种策略参数传递的时间从$\Theta(1)$变成了$\Theta(N)$，因此递归式也变为了$T(n) = T(n/2) + \Theta(N)$，用主方法求出递归式的解为$T(n) = O(N)$。
                  \item 因为子问题的规模为$n$，因此递归式为$T(n) = T(n/2) + \Theta(n)$，递归式的解为$T(n) = O(n)$。
                \end{enumerate}

          \item MERGE-SORT也分为三种传递策略讨论：
                \begin{enumerate}[label=\arabic*)]
                  \item 根据2.3.2节的分析，MERGE-SORT的递归式为$T(n) = 2T(n/2) + \Theta(n)$，递归式的解为$T(n) = \Theta(n\text{lg}n)$。
                  \item 虽然增加了参数传递的时间，但根据2.3.1节中MERGE-SORT的伪代码，递归式仍为$T(n) = 2T(n/2) + \Theta(n)$，因此解依然是$T(n) = \Theta(n\text{lg}n)$。
                  \item 第三种情况其实和第二种很类似，虽然问题规模减小了，但分解--合并所花的时间还是$\Theta(n)$，解依旧是$T(n) = \Theta(n\text{lg}n)$。
                \end{enumerate}
        \end{enumerate}

  \item \textbf{更多递归式的例子}

        {\kaishu 给出下列递归式$T(n)$的渐近上下界。假设对足够小的$n$，$T(n)$是常量。使所给出的界尽量紧确，并加以证明。}

        \begin{enumerate}[label=\alph*)]
          \item $T(n) = 3T(n/2) + n\text{lg}n$

                $f(n) = n\text{lg}n$，$n^{\text{log}_{b}a} = n^{\text{lg}3}$，$\because f(n) = O(n^{\text{log}_{b}a - \varepsilon})$，$\therefore T(n) = \Theta(n^{\text{lg}3})$。

          \item $T(n) = 5T(n/5) + n/\text{lg}n$

                方法同\hyperref[sec:4-4-e]{e)}

          \item $T(n) = 4T(n/2) + n^2\sqrt{n}$

                $f(n) = n^2\sqrt{n}$，$n^{\text{log}_{b}a} = n^2$，$\because f(n) = \Omega(n^{\text{log}_{b}a + \varepsilon}) = \Omega(n^{2 + 1/2})$，且有$af(n/b) \leqslant cf(n)$，$\sqrt{2}/2 \leqslant c < 1$，$\therefore T(n) = \Theta(n^{5/2})$。

          \item $T(n) = 3T(n/3 + 5) + n/2$

                使用递归树方法求解。

          \item \label{sec:4-4-e}$T(n) = 2T(n/2) + n/\text{lg}n$

                使用递归树方法求解，第$i$层结点的值为$\frac{n/2^i}{\text{lg}(n/2^i)}$，最后一层为$n/2^i = 1$，因此递归树一共有$\text{lg}n$层。每一层的结点个数为$2^i$，因此每一层的总代价为$2^i \cdot \frac{n/2^i}{\text{lg}(n/2^i)} = n/(\text{lg}n - i)$。整棵递归树的代价为：
\begin{align}
  T(n) &= \sum_{i=0}^{\text{lg}n-1} \frac{n}{\text{lg}n - i} \nonumber \\
       &= n\sum_{i=1}^{\text{lg}n} \frac{n}{i} \text{（参考自\texttt{"}Instructor's Manual\texttt{"}，但不清楚是怎样得出的）} \nonumber \\
       &= n\sum_{i=1}^{\text{lg}n} \frac{1}{i} \text{（参考自\texttt{"}Instructor's Manual\texttt{"}，但不清楚是怎样得出的）} \nonumber \\
       &= n \cdot \Theta(\text{lg}\text{lg}n) \text{（公式A.7）} \nonumber \\
       &= \Theta(n\text{lg}\text{lg}n)
\end{align}
                证明略。（用数学归纳法分别证明$T(n) \leqslant n(1 + H_{\lfloor \text{lg}n \rfloor})$与$T(n) \geqslant n \cdot H_{\lceil \text{lg}n \rceil}$，$H_k$代表第$k$个调和级数。）

          \item $T(n) = T(n/2) + T(n/4) + T(n/8) + n$

                递归树一共有$\text{lg}n$层，每一层的总代价为$(7/8)^i$，因此递归树的代价为：
\begin{align}
  T(n) &= n\sum_{i=0}^{\text{lg}n} \left(\frac{7}{8}\right)^i \nonumber \\
       &= \Theta(n)
\end{align}
                证明略。

          \item $T(n) = T(n - 1) + 1/n$

                这是调和级数的递归式，根据附录A中的公式A.7，此递归式的渐近上下界为$\Theta(\text{lg}n)$。

          \item $T(n) = T(n - 1) + \text{lg}n$

                猜测此递归式的解为$\Theta(n\text{lg}n)$，需要分别证明$T(n) \leqslant cn\text{lg}n$和$T(n) \geqslant cn\text{lg}n$。

                证明第一个不等式：
\begin{align}
  T(n) &= T(n - 1) + \text{lg}n \nonumber \\
       &\leqslant c(n - 1)\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &= cn\text{lg}(n - 1) - c\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &\leqslant cn\text{lg}(n - 1) - c\text{lg}(n/2) + \text{lg}n \nonumber \\
       &= cn\text{lg}(n - 1) - c\text{lg}n + c + \text{lg}n \nonumber \\
       &< cn\text{lg}n - c\text{lg}n + c + \text{lg}n \nonumber \\
       &\leqslant cn\text{lg}n
\end{align}
                当且仅当$-c\text{lg}n + c + \text{lg}n \leqslant 0$时上式成立。

                证明第二个不等式：
\begin{align}
  T(n) &= T(n - 1) + \text{lg}n \nonumber \\
       &\geqslant c(n - 1)\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &= cn\text{lg}(n - 1) - c\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &\geqslant cn\text{lg}(n/2) - c\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &= cn\text{lg}n - cn - c\text{lg}(n - 1) + \text{lg}n \nonumber \\
       &\geqslant cn\text{lg}n
\end{align}
                当且仅当$-cn - c\text{lg}(n - 1) + \text{lg}n \geqslant 0$时上式成立。

                因此$T(n) = \Theta(n\text{lg}n)$。

          \item $T(n) = T(n - 2) + 2\text{lg}n$

                方法同上。

          \item $T(n) = \sqrt{n}T(\sqrt{n}) + n$

                参考\hyperref[sec:4-1-h]{4-1的h)}及递归树方法。
        \end{enumerate}

  \item \textbf{斐波那契数}

        {\kaishu 我们已在递归式(3.21)中定义了斐波那契数，现在进一步介绍它们的性质。我们将用生成函数技术来解斐波那契递归式。定义生成函数（或形式幂级数）$\mathcal{F}$如下}

\begin{equation*}
  \mathcal{F}(z) = \sum_{i=0}^{\infty} F_{i}z^{i} = 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + 13z^7 + 21z^8 + \cdots
\end{equation*}

        {\kaishu 其中，$F_i$是第$i$个斐波那契数。}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 证明: $\mathcal{F}(z) = z + z\mathcal{F}(z) + z^2\mathcal{F}(z)$。}

          \item {\kaishu 证明}

                \begin{equation*}
                  \mathcal{F}(z) = \frac{z}{1 - z - z^2} = \frac{z}{(1 - \phi{}z)(1 - \hat{\phi}z)} = \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \phi{}z} - \frac{1}{1 - \hat{\phi}z}\right)
                \end{equation*}

                {\kaishu 其中，$\phi = \frac{1 + \sqrt{5}}{2} = 1.61803\cdots$，$\hat{\phi} = \frac{1 - \sqrt{5}}{2} = -0.61803\cdots$。}

          \item {\kaishu 证明}

                \begin{equation*}
                  \mathcal{F}(z) = \sum_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi{}^i - \hat{\phi{}^i})z^i
                \end{equation*}

          \item {\kaishu 证明: 对$i > 0$，$F_i = \phi{}^{i}/\sqrt{5}$截至最近的整数。（提示: $\lvert \hat{\phi} \rvert < 1$）。}

          \item {\kaishu 证明: 对$i \geqslant 0$，$F_{i+2} \geqslant \phi{}^i$。}
        \end{enumerate}

        \begin{enumerate}[label=\alph*)]
          \item \begin{align}
                  z\mathcal{F}(z) &= z^2 + z^3 + 2z^4 + 3z^5 + \cdots \nonumber \\
                  z^2\mathcal{F}(z) &= \qquad \: z^3 + z^4 + 2z^5 + \cdots \nonumber \\
                  \therefore z + z\mathcal{F}(z) + z^2\mathcal{F}(z) &= z + z^2 + 2z^3 + 3z^4 + 5z^5 + \cdots \nonumber \\
                  &= \mathcal{F}(z)
                \end{align}

          \item 根据a)的结论，求出$\mathcal{F}(z) = \frac{z}{1 - z - z^2}$，同时：
\begin{align}
  \frac{z}{(1 - \phi{}z)(1 - \hat{\phi}z)} &= \frac{z}{1 - \hat{\phi}z - \phi{}z + \phi\hat{\phi}z^2} \nonumber \\
  &= \frac{z}{1 - (\phi + \hat{\phi})z + \phi\hat{\phi}z^2} \nonumber \\
  &= \frac{z}{1 - (\frac{1 + \sqrt{5}}{2} + \frac{1 - \sqrt{5}}{2})z + \frac{1 + \sqrt{5}}{2} \cdot \frac{1 - \sqrt{5}}{2} \cdot z^2} \nonumber \\
  &= \frac{z}{1 - z - z^2}
\end{align}
\begin{align}
  \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \phi{}z} - \frac{1}{1 - \hat{\phi}z}\right) &= \frac{1}{\sqrt{5}} \cdot \frac{(\phi{} - \hat{\phi})z}{(1 - \phi{}z)(1 - \hat{\phi}z)} \nonumber \\
  &= \frac{1}{\sqrt{5}} \cdot \frac{\sqrt{5}z}{1 - z - z^2} \nonumber \\
  &= \frac{z}{1 - z - z^2}
\end{align}
                即得证。

          \item 根据公式(3.23)，得证。

          \item 略。

          \item 根据d)的结论，$F_{i+2} = \phi{}^{i+2}/\sqrt{5}$，若结论成立，则：
\begin{align}
  \frac{\phi{}^{i+2}}{\sqrt{5}} &\geqslant \phi{}^i \nonumber \\
  \frac{\phi{}^2}{\sqrt{5}} &\geqslant 1 \nonumber \\
  \left(\frac{1 + \sqrt{5}}{2}\right)^2 &\geqslant \sqrt{5} \nonumber \\
  6 &\geqslant 2\sqrt{5}
\end{align}
                Q.E.D.
        \end{enumerate}

  \item \textbf{VLSI芯片测试}

        {\kaishu Diogenes教授有$n$个被认为是完全相同的VLSI\footnote{\textrm{VLSI代表“超大规模集成”，当今用于制作大多数微处理器的集成电路芯片技术。}}芯片，原则上它们是可以互相测试的。教授的测试装置一次可测二片，当该装置中放有两片芯片时，每一片就对另一片作测试并报告其好坏。一个好的芯片总能够报告另一片的好坏，但一个坏的芯片的结果是不可靠的。这样，每次测试的四种可能结果如下:}

        \begin{table}[H]
          \centering
          \begin{tabular}{lll}
            $A$芯片报告 & $B$芯片报告 & 结论 \\
            \hline
            $B$是好的 & $A$是好的 & 都是好的，或都是坏的 \\
            $B$是好的 & $A$是坏的 & 至少一片是坏的 \\
            $B$是坏的 & $A$是好的 & 至少一片是坏的 \\
            $B$是坏的 & $A$是坏的 & 至少一片是坏的 \\
          \end{tabular}
        \end{table}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 证明若多于$n/2$的芯片是坏的，在这种成对测试方式下，使用任何策略都不能确定哪个芯片是好的。假设坏的芯片可以联合起来欺骗教授。}
          \item {\kaishu 假设有多于$n/2$的芯片是好的，考虑从$n$片中找出一个好芯片的问题。证明$\lfloor n/2 \rfloor$对测试就足以使问题的规模降至近原来的一半。}
          \item {\kaishu 假设多于$n/2$片芯片是好的，证明好的芯片可用$\Theta(n)$对测试找出。给出并解答表达测试次数的递归式。}
        \end{enumerate}

  \item \textbf{Monge矩阵}

        {\kaishu 一个$m\times{}n$的实数矩阵$A$，如果对所有$i$，$j$，$k$和$l$，$1 \leqslant i < k \leqslant m$和$1 \leqslant j < l \leqslant n$，有}

        \begin{equation*}
          A[i, j] + A[k, l] \leqslant A[i, l] + A[k, j]
        \end{equation*}

        {\kaishu 那么，此矩阵$A$为Monge矩阵。换句话说，每当我们从Monge矩阵中挑出两行与两列，并且考虑行列交叉处的4个元素，左上角与右下角元素的和小于或等于左下角与右上角元素的和。例如下面的矩阵是一个Monge阵。}

        \begin{equation*}
          \begin{matrix}
            10 & 17 & 13 & 28 & 23 \\
            17 & 22 & 16 & 29 & 23 \\
            24 & 28 & 22 & 34 & 24 \\
            11 & 13 & 6 & 17 & 7 \\
            45 & 44 & 32 & 37 & 23 \\
            36 & 33 & 19 & 21 & 6 \\
            75 & 66 & 51 & 53 & 34
          \end{matrix}
        \end{equation*}

        \begin{enumerate}[label=\alph*)]
          \item {\kaishu 证明一个矩阵为Monge阵，当且仅当对所有$i = 1$，$2$，$\cdots$，$m - 1$和$j = 1$，$2$，$\cdots$，$n - 1$，有}

                \begin{equation*}
                  A[i, j] + A[i + 1, j + 1] \leqslant A[i, j + 1] + A[i + 1, j]
                \end{equation*}

                {\kaishu （提示: 在“当”部分，对行、列分别使用归纳法。）}

          \item {\kaishu 下面的矩阵不是Monge阵。改变一个元素，把它变成Monge阵（提示: 利用a)的结论）}

                \begin{equation*}
                  \begin{matrix}
                    37 & 23 & 22 & 32 \\
                    21 & 6 & 7 & 10 \\
                    53 & 34 & 30 & 31 \\
                    32 & 13 & 9 & 6 \\
                    43 & 21 & 15 & 8
                  \end{matrix}
                \end{equation*}

          \item {\kaishu 假设$f(i)$是第$i$行包含最左端最小值的列的索引值。证明对任何的$m\times{}n$ Monge矩阵，有$f(1) \leqslant f(2) \leqslant \cdots \leqslant f(m)$。}

          \item {\kaishu 以下是一段关于分治算法的描述，用来计算$m\times{}n$ Monge矩阵$A$的每一行的最左端最小值:}

                {\kaishu 构造一个包含所有$A$的偶数行的子矩阵$A'$。递归地计算$A'$中每一行的最左端最小值。然后计算$A$中奇数行的最左端最小值。}

                {\kaishu 解释如何能在$O(m + n)$时间内计算出$A$的奇数行的最左端最小值？（假设偶数行的最左端最小值已知）}

          \item {\kaishu 写出d)部分所描述算法的运行时间的递归式，并证明其解为$O(m + n\text{log}m)$。}
        \end{enumerate}

        解答参考：\url{http://www.cise.ufl.edu/class/cot5405sp09/hw1_soln.pdf}
\end{enumerate}